#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 heihieyouheihei, Inc. All Rights Reserved 
#
# @Time    : 2024/8/23 23:10
# @Author  : Yuyun
# @File    : leetcode_347_前K个高频元素.py
# @IDE     : PyCharm

"""
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:
输入: nums = [1], k = 1
输出: [1]

提示：
1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
"""

import heapq
from collections import defaultdict
class Solution:

    #   小根堆，时间复杂度O（nlog n）
    def first_K_freq(self, nums, k):
        nums_dict = {}
        #   统计数字频率
        # for x in nums:
        #     if x not in nums_dict.keys():
        #         nums_dict[x] = 1
        #     else:
        #         nums_dict[x] += 1
        """换种写法"""
        for i in range(len(nums)):
            #此处为获取key = num[i]的value，再 + 1；若不存在，则默认为0
            nums_dict[nums[i]] = nums_dict.get(nums[i],0) + 1
        heapq_pq = []
        for key, value in nums_dict.items():
            #   小根堆，默认按照(value, key)中value的值排序
            heapq.heappush(heapq_pq, (value, key))
            #   如果长度大于k，将堆顶（即最小value元组）推出
            if len(heapq_pq) > k:
                heapq.heappop(heapq_pq)
        #   上诉完成后，heapq_pq就是长度 <= k的堆，其中元素即为高频元素

        # result = []
        # for i in range(k):
        #     #   推出value最小元组，故result数组元素的频率(value)由小到大
        #     result[i] = heapq.heappop(heapq_pq)[1]
        # #   高频率元素在数组前列，故进行数组反转
        # result.reverse()
        """换种写法"""
        result = [None] * k
        for i in range(k - 1, -1, -1):
            #直接在反向写入数组
            result[i] = heapq.heappop(heapq_pq)[1]
        return result

    #   字典 + 数组实现
    def first_K_freq_I(self, nums, k):
        nums_dict = defaultdict(int)
        for x in nums:
            nums_dict[x] += 1
        num_freq = list(nums_dict.values())
        #总项数少于k项，返回错误
        if len(num_freq) < k:
            return '共{}项，小于{}项'.format(len(num_freq), k)
        num_freq.sort(reverse=True) #降序排列
        result = []
        i = 0
        for key, value in nums_dict.items():
            while True:
                #   返回前k项
                if i == k:
                    return result
                #   字典值与降序数组比较，相等则存储字典key；降序数组向后移动
                if value == num_freq[i]:
                    result.append(key)
                    i += 1
                #   不相等，退出循环，字典向后移动
                else:
                    break

if __name__ =='__main__':
    nums = list(map(int, input().split(',')))
    k = int(input())
    solution = Solution()
    result = solution.first_K_freq_I(nums, k)
    print(result)